package DP;

/**
 * @author 曹见朋
 * @create 2024-06-11-22:32
 */
public class Main746 {
    // TODO 746. 使用最小花费爬楼梯
    public static int minCostClimbingStairs(int[] cost) {
        // 1. dp数组含义：到达下标i的位置所需要的花费
        int n = cost.length;
        int[] dp = new int[n + 1];
        // 2. 递推公式：dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

        // 3. 初始化
        dp[0] = 0;
        dp[1] = 0;
        // 4. 遍历
        for(int i = 2; i <= n; i++){
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        // 5. 打印

        for(int i = 0; i <= n; i++){
            System.out.print(dp[i] + " ");
        }
        return dp[n];
    }

    public static void main(String[] args) {
        int[] cost = new int[]{10,15,20};
        int result = minCostClimbingStairs(cost);
        System.out.println();
        System.out.println(result);

    }
}
